Network service providers frequently aggregate communication traffic from multiple sources for transmission over a shared, high-bandwidth link. Service providers commonly overbook their available bandwidth in order to maximize utilization of this costly resource. In other words, the sum of the bandwidth that the service provider makes available to all traffic sources may exceed the actual bandwidth available on the shared link. Most of the time, the traffic sources generate less than their full bandwidth allocation, so that the aggregated traffic volume is less than the shared link capacity, and all of the traffic is transmitted over the shared link at the rate at which the traffic is generated by the sources. During periods of peak demand, however, the aggregated traffic volume may exceed the shared link capacity. In this case, at least some of the traffic must be buffered, and frames may be dropped if the buffer overflows.
To determine how bandwidth is to be shared during periods of heavy demand, service providers typically define multiple classes of services, with different bandwidth allocations and priorities. Each class of service (CoS) may have a committed information rate (CIR), which the service provider guarantees to provide, and an excess information rate (EIR), which the service provider provides on a best-efforts basis. (Some classes of service may have only a CIR allocation, or only an EIR allocation.) Each connection served by the service provider belongs to a specific class of service (CoS), which may be specified in a service level agreement (SLA) between the service provider and the customer making the connection. In aggregating traffic for transmission over the shared link, the service provider attempts to ensure that all traffic within the CIR of each connection is transmitted. The service provider then divides any remaining capacity among the connections according to their EIR allocations.
Service providers generally try to allocate their available bandwidth fairly among their customers. For this purpose, incoming data packets arriving from different sources are queued, and the traffic aggregator multiplexes among the queues in accordance with a fair scheduling scheme. Different weights may be assigned to different queues in order to permit different sources to receive different relative shares of the available capacity. Various fair scheduling schemes are known in the art. In Fair Queuing, for example, if there are N active queues at any given time, each queue receives 1/N of the available bandwidth. In Weighted Fair Queuing (WFQ), different queues may have different service shares according to their relative weights. In some applications of WFQ, including some embodiments of the present invention that are described hereinbelow, each source or connection has its own queue, an ill-behaved source (generating more than its fair share of traffic) will only punish itself and not other sources. Weighted Round Robin (WRR) scheduling operates on similar principles.
U.S. Pat. No. 6,157,654, whose disclosure is incorporated herein by reference, describes a method for adaptively assigning queue service weights to an ATM traffic management controller in order to reduce service weight update calculations. The queue weight configuration is performed using a reconfigurable weighted fair queuing controller, wherein bandwidth requirements for each queue may be changed in response to connection setup and release values.